Bit Manipulation

A comprehensive guide to bit manipulation algorithms and techniques for Data Structures and Algorithms.

Table of Contents

1. Binary Basics and Operations
2. Essential Bit Manipulation Techniques
3. Single Number Problems
4. Bit Counting and Parity
5. Power of Two Operations
6. Subset Generation
7. Binary Tree and Graph Applications
8. Advanced Bit Tricks
9. Common Bit Patterns
10. Usage Examples

---

Binary Basics and Operations

Understanding binary representation and basic operations is fundamental to bit manipulation.

Binary Number System

// Binary representation examples
console.log((5).toString(2));    // "101"
console.log((15).toString(2));   // "1111"
console.log(parseInt("101", 2)); // 5

// Common powers of 2
const powers = {
    1: 0b1,        // 2^0 = 1
    2: 0b10,       // 2^1 = 2
    4: 0b100,      // 2^2 = 4
    8: 0b1000,     // 2^3 = 8
    16: 0b10000,   // 2^4 = 16
    32: 0b100000,  // 2^5 = 32
};

Basic Bitwise Operations

// AND (&) - Both bits must be 1
console.log(5 & 3);  // 101 & 011 = 001 = 1

// OR (|) - At least one bit must be 1
console.log(5 | 3);  // 101 | 011 = 111 = 7

// XOR (^) - Bits must be different
console.log(5 ^ 3);  // 101 ^ 011 = 110 = 6

// NOT (~) - Flip all bits
console.log(~5);     // ~101 = ...11111010 = -6 (two's complement)

// Left Shift (<<) - Multiply by 2^n
console.log(5 << 1); // 101 << 1 = 1010 = 10

// Right Shift (>>) - Divide by 2^n
console.log(10 >> 1); // 1010 >> 1 = 101 = 5

// Unsigned Right Shift (>>>) - Fill with zeros
console.log(-5 >>> 1); // Fills with 0s from left

Helper Functions

// Get bit at position i (0-indexed from right)
function getBit(num, i) {
    return (num & (1 << i)) !== 0;
}

// Set bit at position i to 1
function setBit(num, i) {
    return num | (1 << i);
}

// Clear bit at position i (set to 0)
function clearBit(num, i) {
    return num & ~(1 << i);
}

// Toggle bit at position i
function toggleBit(num, i) {
    return num ^ (1 << i);
}

// Update bit at position i with value
function updateBit(num, i, value) {
    return value ? setBit(num, i) : clearBit(num, i);
}

// Print binary representation (for debugging)
function printBinary(num, bits = 8) {
    return num.toString(2).padStart(bits, '0');
}

---

Essential Bit Manipulation Techniques

1. Check if Number is Even or Odd

function isEven(num) {
    return (num & 1) === 0;
}

function isOdd(num) {
    return (num & 1) === 1;
}

Time Complexity: O(1) | Space Complexity: O(1)

2. Multiply and Divide by Powers of 2

// Multiply by 2^n
function multiplyByPowerOf2(num, n) {
    return num << n;
}

// Divide by 2^n
function divideByPowerOf2(num, n) {
    return num >> n;
}

// Examples
console.log(multiplyByPowerOf2(5, 2)); // 5 * 4 = 20
console.log(divideByPowerOf2(20, 2));  // 20 / 4 = 5

3. Swap Two Numbers

function swapWithoutTemp(a, b) {
    a = a ^ b;
    b = a ^ b; // b = (a^b)^b = a
    a = a ^ b; // a = (a^b)^a = b
    return [a, b];
}

// One-liner version
function swap(a, b) {
    return [a ^ b, a ^ (a ^ b)];
}

4. Find Absolute Value

function absoluteValue(num) {
    const mask = num >> 31; // Get sign bit (all 1s if negative, all 0s if positive)
    return (num + mask) ^ mask;
}

5. Check if Two Numbers Have Same Sign

function haveSameSign(a, b) {
    return (a ^ b) >= 0;
}

---

Single Number Problems

These are classic interview problems that showcase the power of XOR operations.

1. Single Number I

Find the number that appears once when all others appear twice:

function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
}

// Example: [2,2,1] → 1
// 2 ^ 2 ^ 1 = 0 ^ 1 = 1

Time Complexity: O(n) | Space Complexity: O(1)

2. Single Number II

Find the number that appears once when all others appear three times:

function singleNumberII(nums) {
    let ones = 0, twos = 0;

    for (const num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }

    return ones;
}

3. Single Number III

Find two numbers that appear once when all others appear twice:

function singleNumberIII(nums) {
    let xor = 0;
    for (const num of nums) {
        xor ^= num;
    }

    // Find rightmost set bit
    const rightmostBit = xor & (-xor);

    let num1 = 0, num2 = 0;
    for (const num of nums) {
        if (num & rightmostBit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }

    return [num1, num2];
}

---

Bit Counting and Parity

1. Count Set Bits (Hamming Weight)

Method 1: Brian Kernighan's Algorithm

function countSetBits(n) {
    let count = 0;
    while (n) {
        n &= (n - 1); // Remove rightmost set bit
        count++;
    }
    return count;
}

Method 2: Built-in Method

function countSetBitsBuiltIn(n) {
    return n.toString(2).split('1').length - 1;
}

Method 3: Lookup Table

function countSetBitsLookup(n) {
    const table = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];
    let count = 0;

    while (n) {
        count += table[n & 0xF]; // Check last 4 bits
        n >>= 4;
    }

    return count;
}

2. Check Parity (Even/Odd number of 1s)

function hasEvenParity(n) {
    let parity = 0;
    while (n) {
        parity ^= 1;
        n &= (n - 1);
    }
    return parity === 0;
}

// Optimized version using built-in
function hasEvenParityFast(n) {
    return (countSetBits(n) & 1) === 0;
}

3. Find Position of Rightmost Set Bit

function rightmostSetBit(n) {
    if (n === 0) return -1;

    // Method 1: Using isolation
    const isolated = n & (-n);
    return Math.log2(isolated);
}

function rightmostSetBitPosition(n) {
    let position = 1;
    while ((n & 1) === 0) {
        n >>= 1;
        position++;
    }
    return position;
}

---

Power of Two Operations

1. Check if Power of Two

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

// Examples:
// 8 = 1000, 8-1 = 0111, 1000 & 0111 = 0000 ✓
// 6 = 0110, 6-1 = 0101, 0110 & 0101 = 0100 ✗

2. Next Power of Two

function nextPowerOfTwo(n) {
    if (n <= 1) return 1;

    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;

    return n + 1;
}

3. Previous Power of Two

function previousPowerOfTwo(n) {
    if (n <= 1) return 1;

    let power = 1;
    while (power * 2 <= n) {
        power *= 2;
    }

    return power;
}

4. Find Log Base 2

function log2Floor(n) {
    if (n <= 0) return -1;

    let result = 0;
    while (n > 1) {
        n >>= 1;
        result++;
    }

    return result;
}

// Using built-in
function log2FloorBuiltIn(n) {
    return Math.floor(Math.log2(n));
}

---

Subset Generation

1. Generate All Subsets

function generateSubsets(nums) {
    const n = nums.length;
    const totalSubsets = 1 << n; // 2^n
    const result = [];

    for (let mask = 0; mask < totalSubsets; mask++) {
        const subset = [];

        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push(nums[i]);
            }
        }

        result.push(subset);
    }

    return result;
}

// Example: [1,2,3] generates:
// 000 → []
// 001 → [1]
// 010 → [2]
// 011 → [1,2]
// 100 → [3]
// 101 → [1,3]
// 110 → [2,3]
// 111 → [1,2,3]

2. Generate K-Size Subsets

function generateKSizeSubsets(nums, k) {
    const n = nums.length;
    const result = [];

    for (let mask = 0; mask < (1 << n); mask++) {
        if (countSetBits(mask) === k) {
            const subset = [];
            for (let i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push(nums[i]);
                }
            }
            result.push(subset);
        }
    }

    return result;
}

3. Iterate Through Subsets of a Set

function iterateSubsets(mask) {
    const subsets = [];
    let submask = mask;

    do {
        subsets.push(submask);
        submask = (submask - 1) & mask;
    } while (submask !== mask);

    return subsets;
}

---

Binary Tree and Graph Applications

1. Binary Tree Path Sum

function hasPathSum(root, targetSum) {
    function dfs(node, currentPath, currentSum) {
        if (!node) return false;

        currentPath = currentPath * 2 + (node.val % 2);
        currentSum += node.val;

        if (!node.left && !node.right) {
            return currentSum === targetSum;
        }

        return dfs(node.left, currentPath, currentSum) ||
               dfs(node.right, currentPath, currentSum);
    }

    return dfs(root, 0, 0);
}

2. Graph Coloring with Bitmask

function canColor(graph, colors) {
    const n = graph.length;
    const dp = new Array(1 << n).fill(0);
    dp[0] = 1;

    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] === 0) continue;

        const node = countSetBits(mask);
        if (node === n) return true;

        for (let color = 1; color <= colors; color++) {
            let canUseColor = true;

            for (let neighbor of graph[node]) {
                if ((mask & (1 << neighbor)) &&
                    ((dp[mask] >> (neighbor * 2)) & 3) === color) {
                    canUseColor = false;
                    break;
                }
            }

            if (canUseColor) {
                const newMask = mask | (1 << node);
                dp[newMask] = dp[mask] | (color << (node * 2));
            }
        }
    }

    return false;
}

3. Traveling Salesman with Bitmask DP

function tsp(graph) {
    const n = graph.length;
    const dp = Array.from({ length: 1 << n },
        () => new Array(n).fill(Infinity));

    dp[1][0] = 0; // Start from city 0

    for (let mask = 1; mask < (1 << n); mask++) {
        for (let u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;

            for (let v = 0; v < n; v++) {
                if (u === v || !(mask & (1 << v))) continue;

                const prevMask = mask ^ (1 << u);
                if (dp[prevMask][v] !== Infinity) {
                    dp[mask][u] = Math.min(dp[mask][u],
                        dp[prevMask][v] + graph[v][u]);
                }
            }
        }
    }

    let result = Infinity;
    const finalMask = (1 << n) - 1;

    for (let i = 1; i < n; i++) {
        if (dp[finalMask][i] !== Infinity) {
            result = Math.min(result, dp[finalMask][i] + graph[i][0]);
        }
    }

    return result;
}

---

Advanced Bit Tricks

1. Reverse Bits

function reverseBits(n) {
    let result = 0;

    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }

    return result >>> 0; // Convert to unsigned 32-bit
}

// Optimized version using lookup table
function reverseBitsLookup(n) {
    const lookup = new Array(256);

    // Initialize lookup table
    for (let i = 0; i < 256; i++) {
        let rev = 0;
        for (let j = 0; j < 8; j++) {
            if (i & (1 << j)) {
                rev |= 1 << (7 - j);
            }
        }
        lookup[i] = rev;
    }

    return (lookup[n & 0xFF] << 24) |
           (lookup[(n >> 8) & 0xFF] << 16) |
           (lookup[(n >> 16) & 0xFF] << 8) |
           (lookup[(n >> 24) & 0xFF]);
}

2. Gray Code Generation

function grayCode(n) {
    const result = [];
    const totalCodes = 1 << n;

    for (let i = 0; i < totalCodes; i++) {
        result.push(i ^ (i >> 1));
    }

    return result;
}

3. Find Missing Number

function findMissingNumber(nums) {
    const n = nums.length;
    let missing = n; // Start with n

    for (let i = 0; i < n; i++) {
        missing ^= i ^ nums[i];
    }

    return missing;
}

4. Maximum XOR of Two Numbers

function findMaximumXOR(nums) {
    let maxResult = 0;
    let mask = 0;

    for (let i = 30; i >= 0; i--) {
        mask |= (1 << i);
        const prefixes = new Set();

        for (const num of nums) {
            prefixes.add(num & mask);
        }

        const candidate = maxResult | (1 << i);

        for (const prefix of prefixes) {
            if (prefixes.has(candidate ^ prefix)) {
                maxResult = candidate;
                break;
            }
        }
    }

    return maxResult;
}

---

Common Bit Patterns

1. Bit Manipulation Patterns

// Check if bit i is set
const isSet = (num, i) => (num & (1 << i)) !== 0;

// Set bit i
const setBit = (num, i) => num | (1 << i);

// Clear bit i
const clearBit = (num, i) => num & ~(1 << i);

// Toggle bit i
const toggleBit = (num, i) => num ^ (1 << i);

// Clear all bits from i to 0
const clearBitsFromITo0 = (num, i) => num & (~((1 << (i + 1)) - 1));

// Clear all bits from MSB to i
const clearBitsFromMSBToI = (num, i) => num & ((1 << i) - 1);

// Get rightmost set bit
const getRightmostSetBit = (num) => num & (-num);

// Clear rightmost set bit
const clearRightmostSetBit = (num) => num & (num - 1);

// Check if only one bit is set (power of 2)
const isOnlyOneBitSet = (num) => num > 0 && (num & (num - 1)) === 0;

2. Common Bitmask Patterns

// Full mask with n bits
const fullMask = (n) => (1 << n) - 1;

// Alternating pattern masks
const alternating1 = 0x55555555; // 01010101...
const alternating2 = 0xAAAAAAAA; // 10101010...

// Every 2nd bit pattern
const every2ndBit = 0x33333333; // 00110011...

// Every 4th bit pattern
const every4thBit = 0x0F0F0F0F; // 00001111...

// Check if mask is subset of another mask
const isSubset = (subset, superset) => (subset & superset) === subset;

// Get complement of mask
const complement = (mask, totalBits) => (~mask) & ((1 << totalBits) - 1);

---

Usage Examples

Here's how to use these bit manipulation techniques:

console.log("=== Bit Manipulation Techniques Demo ===");

// Basic operations
console.log("5 in binary:", printBinary(5, 4));        // 0101
console.log("3 in binary:", printBinary(3, 4));        // 0011
console.log("5 & 3 =", 5 & 3, printBinary(5 & 3, 4)); // 1, 0001
console.log("5 | 3 =", 5 | 3, printBinary(5 | 3, 4)); // 7, 0111
console.log("5 ^ 3 =", 5 ^ 3, printBinary(5 ^ 3, 4)); // 6, 0110

// Bit manipulation functions
console.log("Get bit 2 of 5:", getBit(5, 2));          // true (101, bit 2 is 1)
console.log("Set bit 1 of 5:", setBit(5, 1));          // 7 (101 -> 111)
console.log("Clear bit 2 of 5:", clearBit(5, 2));      // 1 (101 -> 001)
console.log("Toggle bit 1 of 5:", toggleBit(5, 1));    // 7 (101 -> 111)

// Power of 2 operations
console.log("Is 8 power of 2:", isPowerOfTwo(8));      // true
console.log("Is 6 power of 2:", isPowerOfTwo(6));      // false
console.log("Next power of 2 after 10:", nextPowerOfTwo(10)); // 16

// Counting operations
console.log("Count set bits in 7:", countSetBits(7));   // 3 (111 has 3 ones)
console.log("Count set bits in 8:", countSetBits(8));   // 1 (1000 has 1 one)

// Single number problems
console.log("Single number in [2,2,1]:", singleNumber([2,2,1])); // 1
console.log("Single numbers in [1,2,1,3,2,5]:", singleNumberIII([1,2,1,3,2,5])); // [3,5]

// Subset generation
const nums = [1, 2, 3];
console.log("All subsets of [1,2,3]:", generateSubsets(nums));

// Advanced operations
console.log("Reverse bits of 5:", reverseBits(5));
console.log("Gray code for n=3:", grayCode(3));

// Swap without temp
let a = 10, b = 20;
[a, b] = swapWithoutTemp(a, b);
console.log("After swap:", a, b); // 20, 10

// Missing number
console.log("Missing number in [3,0,1]:", findMissingNumber([3,0,1])); // 2

// Practical applications
const bitmask = 0b1011; // 11 in decimal
console.log("Iterating through subsets of", printBinary(bitmask, 4));
const subsets = iterateSubsets(bitmask);
subsets.forEach(subset => console.log("  Subset:", printBinary(subset, 4)));

---

Time Complexity Summary

Operation	Time Complexity	Space Complexity
Basic Bit Operations	O(1)	O(1)
Count Set Bits	O(log n)	O(1)
Check Power of 2	O(1)	O(1)
Generate All Subsets	O(n × 2^n)	O(2^n)
Single Number	O(n)	O(1)
Reverse Bits	O(log n)	O(1)
Find Maximum XOR	O(n × log(max))	O(n)
Gray Code	O(2^n)	O(2^n)
Missing Number	O(n)	O(1)
Subset Iteration	O(3^n)	O(1)

---

Key Patterns to Remember

1. XOR Properties

• a ^ a = 0
• a ^ 0 = a
• XOR is commutative and associative
• Perfect for finding single numbers

2. Bit Isolation

// Get rightmost set bit
const rightmost = n & (-n);

// Clear rightmost set bit
const cleared = n & (n - 1);

3. Power of 2 Check

const isPowerOf2 = n > 0 && (n & (n - 1)) === 0;

4. Bitmask for Subsets

// Check if element i is in subset
const inSubset = (mask, i) => (mask & (1 << i)) !== 0;

5. Bit Counting Optimization

Use Brian Kernighan's algorithm: n & (n-1) removes rightmost set bit

---

Common Interview Patterns

1. State Compression

• Use bitmasks to represent states in DP
• Traveling salesman, subset sum, etc.

2. Set Operations

• Union: a | b
• Intersection: a & b
• Difference: a & (~b)

3. Parity and Checksums

• XOR for detecting errors
• Even/odd parity checks

4. Optimization Tricks

• Multiply/divide by powers of 2 using shifts
• Swap without temporary variables
• Fast modulo for powers of 2: n & (p-1) where p is power of 2

---

Interview Tips

1. Master the basics: AND, OR, XOR, shifts
2. Know common patterns: Power of 2, bit counting, XOR properties
3. Practice visualization: Draw out bit patterns
4. Handle edge cases: Zero, negative numbers, overflow
5. Optimize when possible: Bit operations are faster than arithmetic
6. Use built-in functions wisely: Sometimes clarity is better than bit tricks